package manaul;
import java.lang.Math;
import java.lang.Math;
import edu.princeton.cs.algs4.StdOut;

public class C1_24 {
	
	public static int Count=0;
	public static int eculd(int a, int b) {
		if (a>b)
		{
			if (b==0)
			{
				StdOut.printf("最大公约数:%d\n",a);
				return a;
				
			}
			else {
				int r=Math.floorMod(a, b);
				a=b;
				b=r;
				StdOut.printf("a: %d,b: %d\n",a,b);
				return eculd(a, b);
			}
		}
		else {
			return eculd(b, a);
		}
		
	}
	//27
	public static double binomial(int N, int k, double p)
	{
		Count++;
	if (N == 0 && k == 0) return 1.0; else if (N < 0 || k < 0) return 0.0;
	return (1.0 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1,p);
	}
	public static double[][] M;
	public static double Binomial(int N, int k, double p) {
		M = new double[N + 1][k + 1];
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= k; j++) {
				M[i][j] = -1;
			}
		}
		return binomialu(N, k, p);
	}
	public static double binomialu(int N, int k, double p) {
		Count++;
		if (N == 0 && k == 0) {
			return 1.0;
		}
		if (N < 0 || k < 0) {
			return 0.0;
		}
		if (M[N][k] == -1) {  
			M[N][k] = (1.0 - p) * binomialu(N - 1, k, p) + p * binomialu(N - 1, k - 1, p);
		}
		return M[N][k];

	}


	public static void main(String[] args) {
		eculd(1111111, 1234567);
		//binomial(100, 50, 0.1);
		//StdOut.println(Count);
		double c= Binomial(100, 50, 0.3);
		StdOut.printf("count: %d",Count);
	}

}
